package LinkedList;

/**
 *  反转链表
 *  ===> 给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
 */
public class InvertList {
    /**
     * 核心思想 ：
     * 由于反转链表（即，为将当前节点的next指针指向链表中前一个元素）；
     * 同时，由于原本链表的最后next指针指向的是null，
     * 若仅仅使用prev，now指针的话，若是倒数第二个节点指向其前面的节点的话，即无法获取最后一个节点
     * ===> 即，需要使用prev（前一个），now（目前），next（下一个）指针
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        // 即，在遍历整个链表时，利用三个指针prev，now，next，来记录当前节点，当前节点的前一个节点以及当前节点的下一个节点
//        ListNode prev = null;
//        ListNode now = head;
//        while(now != null){
//            ListNode next = now.next;
//            now.next = prev;
//            // 遍历链表
//            prev = now;
//            now = next;
//        }
//        return prev;

        /**
         *  递归思想 ：
         *  即，当遍历链表时，递归将当前节点的下一个节点的next指针指向当前节点
         *  需要注意的是 ：
         *   下一个节点必须指向∅。如果忽略了这一点，链表中可能会产生环。
         */
        if (head == null || head.next == null){ // head == null为应对 链表为空 的特殊情况
            return head;
        }
        // 考虑 ：为何此处要使用node节点，来记录reverseList递归函数的值
        // 原因 ：为了记录头节点（即，从第一次return开始，后面每次返回的值，皆为原本链表的尾节点）
        ListNode node = reverseList(head.next);
//        System.out.println(node.next);
        head.next.next = head; // 即，此处将当前节点的下一个节点的next指针指向当前节点
        head.next = null; // 若是当前节点的next指针还是指向原本的下一个节点的话，会形成环
        return node;
    }
}
